package huawei.bfs;

/**
 * https://leetcode-cn.com/problems/perfect-squares/
 *
 * 数学方法 四平方数定理解决 https://baike.baidu.com/item/%E5%9B%9B%E5%B9%B3%E6%96%B9%E5%92%8C%E5%AE%9A%E7%90%86
 */
public class J279 {
    public static void main(String[] args){
        System.out.println(numSquares(12));
        System.out.println(numSquares(13));
        System.out.println(numSquares(56));
    }
    public static int numSquares(int n) {
        int[] dp=new int[n+1];
        for (int i = 1; i < n+1; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j*j <= i; j++) {
                min=Math.min(min,dp[i-j*j]);
            }
            dp[i]=min+1;
        }
        return dp[n];
    }
    public static int numSquares2(int n) {
        if(isSq(n)){
            return 1;
        }
        if(isFour(n)){
            return 4;
        }
        for (int i = 1; i*i <n ; i++) {
            int tmp = n-i*i;
            if(isSq(tmp)){
                return 2;
            }
        }
        return 3;
    }
    private static boolean isSq(int num){
        int tmp = (int) Math.sqrt(num);
        return tmp*tmp==num;
    }

    /**
     * 四平方数定理, x=4^k(8m+7),x可分解为四个数
     * @param num
     * @return
     */
    private  static boolean isFour(int num){
        while (num%4==0){
            num=num>>2;
        }
        return (num-7)%8==0;
    }
}
